package com.mdnote.practice.bit;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/17
 * @description 比特位计数
 */
public class LeetCode338 {


    public int[] countBits(int num) {

        int[] dp = new int[num + 1];

        int i = 0, b = 1;
        while (b <= num) {

            // P(x+b)=P(x)+1,b=2m>x
            while (i < b && i + b <= num) {
                dp[i + b] = dp[i] + 1;
                i ++;
            }
            i = 0;
            b <<= 2;
        }

        return dp;
    }
}
